C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/vol_200/252_01/chap12.txt

Text File | 1990-02-13 | 23.0 KB | 530 lines

                                                   Chapter 12
                                           DYNAMIC ALLOCATION



WHAT IS DYNAMIC ALLOCATION?
____________________________________________________________

Dynamic allocation is very intimidating to a    =============
person the first time he comes across it, but     DYNLIST.C
that need not be.  Simply relax and read this   =============
chapter carefully and you will have a good
grounding in a very valuable programming
resource.  All of the variables in every program up to this
point have been static variables as far as we are concerned.
(Actually, some of them have been automatic and were
dynamically allocated for you by the system, but it was
transparent to you.)  In this chapter, we will study some
dynamically allocated variables.  They are variables that do
not exist when the program is loaded, but are created
dynamically as they are needed.  It is possible, using these
techniques, to create as many variables as needed, use them,
and deallocate their space for use by other variables.  As
usual, the best teacher is an example, so examine the program
named DYNLIST.C.

We begin by defining a named structure animal with a few
fields pertaining to dogs.  We do not define any variables of
this type, only three pointers.  If you search through the
remainder of the program, you will find no variables defined
so we have nothing to store data in.  All we have to work with
are three pointers, each of which point to the defined
structure.  In order to do anything, we need some variables,
so we will create some dynamically.



DYNAMIC VARIABLE CREATION
____________________________________________________________

The statement in line 14, which assigns something to the
pointer pet1 will create a dynamic structure containing three
variables.  The heart of the statement is the malloc()
function buried in the middle of the statement.  This is a
memory allocate function that needs the other things to
completely define it.  The malloc() function, by default, will
allocate a piece of memory on a heap that is "n" characters
in length and will be of type character.  The "n" must be
specified as the only argument to the function.  We will
discuss "n" shortly, but first we need to define a heap.




                                                    Page 12-1

                              Chapter 12 - Dynamic Allocation

WHAT IS A HEAP?
____________________________________________________________

Every compiler has a set of limitations on it as to how big
the executable file can be, how many variables can be used,
how long the source file can be, etc.  One limitation placed
on users by most MS-DOS C compilers is a limit of 64K for the
executable code if you happen to be in the small memory model.
This is because the IBM-PC uses a microprocessor with a 64K
segment size, and it requires special calls to use data
outside of a single segment.  In order to keep the program
small and efficient, these calls are not used in some MS-DOS
implementations of C, and the memory space is limited but
still adequate for most programs.

A heap is an area outside of this 64K boundary which can be
accessed by the program to store data and variables.  The data
and variables are put on the heap by the system as calls to
malloc() are made.  The system keeps track of where the data
is stored.  Data and variables can be deallocated as desired
leading to holes in the heap.  The system knows where the
holes are and will use them for additional data storage as
more malloc() calls are made.  The structure of the heap is
therefore a very dynamic entity, changing constantly.


MORE ABOUT SEGMENTS
____________________________________________________________

Most C compilers give the user a choice of memory models to
use.  The user has a choice of using a model with a 64K
limitation for either program or data leading to a small fast
program or selecting a 640K limitation and requiring longer
address calls leading to less efficient addressing.  Using the
larger address space requires inter segment addressing,
resulting in the slightly slower running time.  The time is
probably insignificant in most programs, but there are other
considerations.

If a program uses no more than 64K bytes for the total of its
code and memory and if it doesn't use a stack, it can be made
into a .COM file.  Since a .COM file is already in a memory
image format, it can be loaded very quickly whereas a file in
an .EXE format must have its addresses relocated as it is
loaded.  Therefore a tiny memory model can generate a program
that loads faster than one generated with a larger memory
model.  Don't let this worry you, it is a fine point that few
programmers worry about.

Using dynamic allocation, it is possible to store the data on
the heap and that may be enough to allow you to use the small
memory model.  Of course, you wouldn't store local variables
such as counters and indexes on the heap, only very large
arrays or structures.

                                                    Page 12-2

                              Chapter 12 - Dynamic Allocation


Even more important than the need to stay within the small
memory model is the need to stay within the computer.  If you
had a program that used several large data storage areas, but
not at the same time, you could load one block storing it
dynamically, then get rid of it and reuse the space for the
next large block of data.  Dynamically storing each block of
data in succession, and using the same storage for each block
may allow you to run your entire program in the computer
without breaking it up into smaller programs.



BACK TO THE MALLOC FUNCTION
____________________________________________________________

Hopefully the above description of the heap and the overall
plan for dynamic allocation helped you to understand what we
are doing with the malloc() function.  It simply asks the
system for a block of memory of the size specified, and gets
the block with the pointer pointing to the first element of
the block.  The only argument in the parentheses is the size
of the block desired and in our present case, we desire a
block that will hold one of the structures we defined at the
beginning of the program.  The sizeof operator is new, new to
us at least.  It returns the size in bytes of the argument
within its parentheses.  It therefore, returns the size of the
structure named animal, in bytes, and that number is sent to
the system with the malloc() call.  At the completion of that
call, we have a block on the heap allocated to us, with pet1
pointing to the block of data.



WHAT IS A CAST?
____________________________________________________________

We still have a funny looking construct at the beginning of
the malloc() function call.  That is called a cast.  The
malloc() function returns a block with the pointer pointing
to it being a pointer to type void by default.  You really
cannot use a pointer to void, so it must be changed to some
other type.  You can define the pointer type with the
construct given on the example line.  In this case we want the
pointer to point to a structure of type animal, so we tell the
compiler with this strange looking construct.  Even if you
omit the cast, most compilers will return a pointer correctly,
give you a warning, and go on to produce a working program.
It is better programming practice to provide the compiler with
the cast to prevent getting the warning message.  The data
space of the computer is depicted graphically by figure 12-1.




                                                    Page 12-3

                              Chapter 12 - Dynamic Allocation

USING THE DYNAMICALLY ALLOCATED STRUCTURE
____________________________________________________________

If you remember our studies of structures and pointers, you
will recall that if we have a structure with a pointer
pointing to it, we can access any of the variables within the
structure.  In lines 15 through 17 of the program, we assign
some silly data to the structure for illustration.  It should
come as no surprise to you that these assignment statements
look just like assignments to statically defined variables.
Figure 12-2 illustrates the state of the data space at this
point in the program execution.

In the next statement, we assign the value of pet1 to pet2
also.  This creates no new data, we simply have two pointers
to the same object.  Since pet2 is pointing to the structure
we created above, pet1 can be reused to get another
dynamically allocated structure which is just what we do next.
Keep in mind that pet2 could have just as easily been used for
the new allocation.  The new structure is filled with silly
data for illustration.

Finally, we allocate another block on the heap using the
pointer pet3, and fill its block with illustrative data.
Figure 12-3 illustrates the condition of the data space
following execution of line 29 of the program.

Printing the data out should pose no problem to you since
there is nothing new in the three print statements.  It is
left for you to study.

Even though it is not illustrated in this tutorial, you can
dynamically allocate and use simple variables such as a single
char type variable.  This should be discouraged however since
it is very inefficient.


GETTING RID OF THE DYNAMICALLY ALLOCATED DATA
____________________________________________________________

Another new function is used to get rid of the data and free
up the space on the heap for reuse, the function free().  To
use it, you simply call it with the pointer to the block as
the only argument, and the block is deallocated.

In order to illustrate another aspect of the dynamic
allocation and deallocation of data, an additional step is
included in the program on your monitor.  The pointer pet1 is
assigned the value of pet3 in line 42.  In doing this, the
block that pet1 was pointing to is effectively lost since
there is no pointer that is now pointing to that block.  It
can therefore never again be referred to, changed, or disposed
of.  That memory, which is a block on the heap, is wasted from
this point on.  This is not something that you would ever

                                                    Page 12-4

                              Chapter 12 - Dynamic Allocation

purposely do in a program.  It is only done here for
illustration.

The first free() function call removes the block of data that
pet1 and pet3 were pointing to, and the second free() call
removes the block of data that pet2 was pointing to.  We
therefore have lost access to all of our data generated
earlier.  There is still one block of data that is on the heap
but there is no pointer to it since we lost the address to it.
Figure 12-4 illustrates the data space as it now appears.
Trying to free the data pointed to by pet1 would result in an
error because it has already been freed by the use of pet3.
There is no need to worry, when we return to DOS, the entire
heap will be disposed of with no regard to what we have put
on it.  The point does need to made that, if you lose a
pointer to a block of the heap, it forever removes that block
of data storage from our use and we may need that storage
later.

Compile and run the program to see if it does what you think
it should do based on this discussion.


THAT WAS A LOT OF DISCUSSION
____________________________________________________________

It took six pages to get through the discussion of the last
program but it was time well spent.  It should be somewhat
exciting to you to know that there is nothing else to learn
about dynamic allocation, the last six pages covered it all.
Of course, there is a lot to learn about the technique of
using dynamic allocation, and for that reason, there are two
more example programs to study.  But the fact remains, there
is nothing more to learn about dynamic allocation than what
was given so far in this chapter.


AN ARRAY OF POINTERS
____________________________________________________________

Load and display the file BIGDYNL.C for         =============
another example of dynamic allocation.  This      BIGDYNL.C
program is very similar to the last one since   =============
we use the same structure, but this time we
define an array of pointers to illustrate the
means by which you could build a large database using an array
of pointers rather than a single pointer to each element.  To
keep it simple we define 12 elements in the array and another
working pointer named point.

The *pet[12] is new to you so a few words would be in order.
What we have defined is an array of 12 pointers, the first
being pet[0], and the last pet[11].  Actually, since an array
is itself a pointer, the name pet by itself is a pointer to

                                                    Page 12-5

                              Chapter 12 - Dynamic Allocation

a pointer.  This is valid in C, and in fact you can go farther
if needed but you will get quickly confused.  I know of no
limit as to how many levels of pointing are possible, so a
definition such as int ****pt; is legal as a pointer to a
pointer to a pointer to a pointer to an integer type variable,
if I counted right.  Such usage is discouraged until you gain
considerable experience.

Now that we have 12 pointers which can be used like any other
pointer, it is a simple matter to write a loop to allocate a
data block dynamically for each and to fill the respective
fields with any data desirable.  In this case, the fields are
filled with simple data for illustrative purposes, but we
could be reading in a database, readings from some test
equipment, or any other source of data.

A few fields are randomly picked in lines 23 through 25 to
receive other data to illustrate that simple assignments can
be used, and the data is printed out to the monitor.  The
pointer point is used in the printout loop only to serve as
an illustration, the data could have been easily printed using
the pet[n] means of definition.  Finally, all 12 blocks of
data are freed before terminating the program.

Compile and run this program to aid in understanding this
technique.  As stated earlier, there was nothing new here
about dynamic allocation, only about an array of pointers.


A LINKED LIST
____________________________________________________________

We finally come to the grandaddy of all         =============
programming techniques as far as being            DYNLINK.C
intimidating.  Load the program DYNLINK.C for   =============
an example of a dynamically allocated linked
list.  It sounds terrible, but after a little
time spent with it, you will see that it is simply another
programming technique made up of simple components that can
be a powerful tool.

In order to set your mind at ease, consider the linked list
you used when you were a child.  Your sister gave you your
birthday present, and when you opened it, you found a note
that said, "Look in the hall closet."  You went to the hall
closet, and found another note that said, "Look behind the TV
set."  Behind the TV you found another note that said, "Look
under the coffee pot."  You continued this search, and finally
you found your pair of socks under the dogs feeding dish.
What you actually did was to execute a linked list, the
starting point being the wrapped present and the ending point
being under the dogs feeding dish.  The list ended at the dogs
feeding dish since there were no more notes.


                                                    Page 12-6

                              Chapter 12 - Dynamic Allocation

In the program DYNLINK.C, we will be doing the same thing your
sister forced you to do.  However, we will do it much faster
and we will leave a little pile of data at each of the
intermediate points along the way.  We will also have the
capability to return to the beginning and traverse the entire
list again and again if we so desire.


THE DATA DEFINITIONS
____________________________________________________________

This program starts similarly to the last two with the
addition of the definition of a constant to be used later.
The structure is nearly the same as that used in the last two
programs except for the addition of another field within the
structure in line 13, the pointer.  This pointer is a pointer
to another structure of this same type and will be used to
point to the next structure in order.  To continue the above
analogy, this pointer will point to the next note, which in
turn will contain a pointer to the next note after that.

We define three pointers to this structure for use in the
program, and one integer to be used as a counter, and we are
ready to begin using the defined structure for whatever
purpose we desire.  In this case, we will once again generate
nonsense data for illustrative purposes.


THE FIRST FIELD
____________________________________________________________

Using the malloc() function, we request a block of storage on
the heap and fill it with data.  The additional field in this
example, the pointer, is assigned the value of NULL, which is
only used to indicate that this is the end of the list.  We
will leave the pointer named start pointing at this structure,
so that it will always point to the first structure of the
list.  We also assign prior the value of start for reasons we
will see soon.  Keep in mind that the end points of a linked
list will always have to be handled differently than those in
the middle of a list.  We have a single element of our list
now and it is filled with representative data.  Figure 12-5
is the graphical representation of the data space following
execution of line 24.


FILLING ADDITIONAL STRUCTURES
____________________________________________________________

The next group of assignments and control statements are
included within a for loop so we can build our list fast once
it is defined.  We will go through the loop a number of times
equal to the constant RECORDS defined at the beginning of our
program.  Each time through, we allocate memory, fill the

                                                    Page 12-7

                              Chapter 12 - Dynamic Allocation

first three fields with nonsense, and fill the pointers.  The
pointer in the last record is given the address of this new
record because the prior pointer is pointing to the prior
record.  Thus prior->next is given the address of the new
record we have just filled.  The pointer in the new record is
assigned the value NULL, and the pointer prior is given the
address of this new record because the next time we create a
record, this one will be the prior one at that time.  That may
sound confusing but it really does make sense if you spend
some time studying it.

Figure 12-6 illustrates the data space following execution of
the loop two times.  The list is growing downward by one
element each time we execute the statements in the loop.  When
we have gone through the for loop 6 times, we will have a list
of 7 structures including the one we generated prior to the
loop.  The list will have the following characteristics.

1.   The pointer named start points to the first structure in
     the list.

2.   Each structure contains a pointer to the next structure.

3.   The last structure has a pointer containing the value
     NULL and can be used to detect the end.

It should be clear to you, if you understand the overall data
structure, that it is not possible to simply jump into the
middle of the list and change a few values.  The only way to
get to the third structure is by starting at the beginning and
working your way down through the list one record at a time.
Although this may seem like a large price to pay for the
convenience of putting so much data outside of the program
area, it is actually a very good way to store some kinds of
data.

A word processor would be a good application for this type of
data structure because you would never need to have random
access to the data.  In actual practice, this is the basic
type of storage used for the text in a word processor with
one line of text per record.  Actually, a program with any
degree of sophistication would use a doubly linked list.  This
would be a list with two pointers per record, one pointing
down to the next record, and the other pointing up to the
record just prior to the one in question.  Using this kind of
a record structure would allow traversing the data in either
direction.


PRINTING THE DATA OUT
____________________________________________________________

To print the data out, a similar method is used as that used
to generate the data.  The pointers are initialized and are

                                                    Page 12-8

                              Chapter 12 - Dynamic Allocation

then used to go from record to record reading and displaying
each record one at a time.  Printing is terminated when the
NULL in the last record is found, so the program doesn't even
need to know how many records are in the list.  Finally, the
entire list is deleted to make room in memory for any
additional data that may be needed, in this case, none.  Care
must be taken to assure that the last record is not deleted
before the NULL is checked.  Once the data is gone, it is
impossible to know if you are finished yet.


MORE ABOUT DYNAMIC ALLOCATION AND LINKED LISTS
____________________________________________________________

It is not difficult, nor is it trivial, to add elements into
the middle of a linked list.  It is necessary to create the
new record, fill it with data, and point its pointer to the
record it is desired to precede.  If the new record is to be
installed between the 3rd and 4th, for example, it is
necessary for the new record to point to the 4th record, and
the pointer in the 3rd record must point to the new one.
Adding a new record to the beginning or end of a list are each
special cases.  Consider what must be done to add a new record
in a doubly linked list.

Entire books are written describing different types of linked
lists and how to use them, so no further detail will be given.
The amount of detail given should be sufficient for a
beginning understanding of C and its capabilities.


ANOTHER NEW FUNCTION - calloc()
____________________________________________________________

One more function must be mentioned, the calloc() function.
This function allocates a block of memory and clears it to all
zeros which may be useful in some circumstances.  It is
similar to malloc and will be left as an exercise for you to
read about and use calloc() if you desire.


PROGRAMMING EXERCISES
____________________________________________________________

1.   Rewrite the example program STRUCT1.C from chapter 11 to
     dynamically allocate the two structures.

2.   Rewrite the example program STRUCT2.C from chapter 11 to
     dynamically allocate the 12 structures.




                                                    Page 12-9